#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 为了验证
vector<int> randomArray(int n, int v) 
{
    vector<int> arr(n);
    for (int i = 0; i < n; i++) 
    {
        arr[i] = rand() % v + 1;
    }
    return arr;
}

// 为了验证
// 保证 arr 有序，才能用这个方法
int right(vector<int>& arr, int num) 
{
    for (int i = 0; i < arr.size(); i++) 
    {
        if (arr[i] >= num) return i;
    }
    return -1;
}

// 保证 arr 有序，才能用这个方法
// 有序数组中找 >=num 的最左位置
int findLeft(vector<int>& arr, int num) 
{
    int l = 0, r = arr.size() - 1, m = 0;
    int ans = -1;
    while (l <= r) 
    {
        // m = (l + r) / 2;
        // m = l + (r - l) / 2;
        m = l + ((r - l) >> 1);
        if (arr[m] >= num) 
        {
            ans = m;
            r = m - 1;
        } 
        else l = m + 1;
    }
    return ans;
}

// 为了验证
int main() 
{
    int N = 100;
    int V = 1000;
    int testTime = 500000;
    cout << "测试开始" << endl;
    for (int i = 0; i < testTime; i++) 
    {
        int n = rand() % N;
        vector<int>&& arr = randomArray(n, V);
        sort(arr.begin(), arr.end());
        int num = rand() % N;
        if (right(arr, num) != findLeft(arr, num)) 
        {
            cout << "出错了!" << endl;
        }
    }
    cout << "测试结束" << endl;
    return 0;
}
